package com.company.Search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}16:49
 */
public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,1000,1000,1000,1234};
        List<Integer> list = binarySearch2(arr,0,arr.length-1,1000);
        System.out.println(list);
    }

    public static int binarySearch(int[] arr,int left,int right,int findValue){
        int mid = (left+right)/2;
        if (arr[mid] == findValue){
            return mid;
        }else if (arr[mid] > findValue){
            return binarySearch(arr,left,mid,findValue);
        }else if (arr[mid] < findValue){
            return binarySearch(arr,mid+1,right,findValue);
        }else {
            return -1;
        }
    }

    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findValue){
        int mid = (left+right)/2;
        if (arr[mid] == findValue){
            List<Integer> resIndexList = new ArrayList<>();
            int temp = mid - 1;
            while (true){
                if (temp < 0 || arr[temp] != findValue){
                    break;
                }
                resIndexList.add(temp);
                temp--;
            }

            resIndexList.add(mid);
            temp = mid + 1;
            while (true){
                if (temp > arr.length - 1 || arr[temp] != findValue){
                    break;
                }
                resIndexList.add(temp);
                temp++;
            }

            return resIndexList;
        }else if (arr[mid] > findValue){
            return binarySearch2(arr,left,mid,findValue);
        }else if (arr[mid] < findValue){
            return binarySearch2(arr,mid+1,right,findValue);
        }else {
            return null;
        }
    }
}
